import binarySearchTree.BinarySearchTree;
import demo1.HashBuck2;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wx
 * Date: 2024-05-02
 * Time: 12:17
 */

class Student {
    public String id ;

    public Student(String id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class Test {


    public List<String> topKFrequent(String[] words, int k) {
        //1.先统计单词出现的次数 -> 存储到map当中
        Map<String,Integer> map = new HashMap<>();
        for (String word: words) {
            if (map.get(word) == null) {
                map.put(word, 1);
            }else {
                Integer val = map.get(word);
                map.put(word, val + 1);
            }
        }
        //2.遍历统计好的Map,把每组数据存储到小根堆当中
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //放元素的时候,如果频率相同,转变为大根堆,按单词的字典序
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                // 要找最大的频率的单词
                Map.Entry<String, Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    if(top.getValue().compareTo(entry.getValue()) == 0){
                       if(top.getKey().compareTo(entry.getKey()) > 0){
                           minHeap.poll();
                           minHeap.offer(entry);
                       }
                    }
                }

            }
        }
        List<String> ret = new ArrayList<>();
        //放到小根堆
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }

    public static void main9(String[] args) {
        int[] array = {1,2,3,3,4,1};
        Map<Integer,Integer> map = new HashMap<>();
        for (Integer x : array) {
            if(map.get(x) == null) {
                //第一次存放
                map.put(x, 1);
            }else {
                //再原来的情况下加一
                int val = map.get(x);
                map.put(x, val + 1);
            }
        }
        for(Map.Entry<Integer, Integer> entry: map.entrySet()) {
            System.out.println("key: " + entry.getKey() + " val: " + entry.getValue());
        }
    }
    public static void main8(String[] args) {
        int[] array = {1,2,3,3,4,1};
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);

    }
    public static void main7(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1,str2);
        }
    }

    private static void func(String str1, String str2) {
        HashSet<Character> set = new HashSet<>();
        for(char ch : str2.toUpperCase().toCharArray()){
            set.add(ch);
        }

        HashSet<Character> set2 = new HashSet<>();
        for(char ch : str1.toUpperCase().toCharArray()){
            if(!set.contains(ch) && !set2.contains(ch)){
                //输出重复字符串
                System.out.print(ch);
                set2.add(ch);
            }
        }
    }


    public static void main6(String[] args) {
        Student student1 = new Student("610324");
        Student student2 = new Student("610324");
        HashBuck2<Student,Integer> hashBuck2 = new HashBuck2<>();
        hashBuck2.put(student1,10);
        Integer val = hashBuck2.getVal(student2);
        System.out.println(val);

    }
    public static void main5(String[] args) {

        Student student1 = new Student("610324");
        Student student2 = new Student("610324");

        System.out.println(student1.hashCode());//x%len
        //System.out.println(student2.hashCode());

        HashMap<Student,Integer> map = new HashMap<>();
        map.put(student1,2);
        Integer ret= map.get(student2);
        System.out.println(ret);

//        HashMap<Student,Integer> map = new HashMap<>();
//        map.put(new Student("610324"),2);//hashcode
//        map.put(new Student("610324"),2);



    }
    public static void main4(String[] args) {
        HashMap<String,Integer> map = new HashMap<>();
        map.put("alc",10);
        map.put("an",12);
        map.put("ana",11);
        map.put("aaw",15);

        Integer val = map.get("alc");
        System.out.println(val);

        System.out.println(map);//存入顺序和打印顺序可能不同


        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            System.out.println("key" + entry.getKey() + " val" + entry.getValue());
        }
        //不支持迭代器遍历
        HashMap<Student,Integer> map2 = new HashMap<>();
        map2.put(new Student("111"),2);//转换用hashcode方法
        //TreeMap 会报错,HashMap不会报错

        //HashMap不会报类型转换异常;只会放到指定位置
        //Set底层是HashMap,所以HashMap和也是一样的
        //每次存储value,默认的value其实就是一个Object对象

    }
    public static void main3(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("sunny");
        set.add("hello");
        set.add("the");

        System.out.println(set);


        Iterator<String> iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //搜索树 -> TreeMap,TreeSet
    }
    public static void main2(String[] args) {
        Map<String,Integer> map = new TreeMap<>();

        map.put("sunny",3);
        map.put("the",5);
        map.put("hello",2);

        System.out.println(map.getOrDefault("whe2", 999999999));
        System.out.println(map.get("the"));

        Set<String> set = map.keySet();
        System.out.println(set);

        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        System.out.println("===============================");
        for (Map.Entry<String, Integer> entry : entrySet) {
            System.out.println("key" + entry.getKey() + "value" + entry.getValue());
        }
        System.out.println("==================================");


        Map<String,Integer> map2 = new HashMap<>();

    }
    public static void main1(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] array = {5,4,3,11,79,15};
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        System.out.println(binarySearchTree.search(11));
        System.out.println(binarySearchTree.search(111));
    }
}
